class Solution {

    //一和零
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len + 1][m + 1][n + 1];
        for(int i = 1; i <= len; i++){
            for(int j = 0; j <= m; j++){
                for(int k = 0; k <= n; k++){
                    int a = zeroCount(strs[i - 1]);
                    int b = strs[i - 1].length() - a;
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(j - a >= 0 && k - b >= 0){
                        dp[i][j][k] = Math.max(dp[i][j][k], dp[i - 1][j - a][k - b] + 1);
                    }
                }
            }
        }
        return dp[len][m][n];
    }

    //一和零(空间优化)
    public int findMaxForm2(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= len; i++){
            for(int j = m; j >= 0; j--){
                for(int k = n; k >= 0; k--){
                    int a = zeroCount(strs[i - 1]);
                    int b = strs[i - 1].length() - a;
                    if(j - a >= 0 && k - b >= 0){
                        dp[j][k] = Math.max(dp[j][k], dp[j - a][k - b] + 1);
                    }
                }
            }
        }
        return dp[m][n];
    }
    public int zeroCount(String s){
        int a = 0;
        char[] chs = s.toCharArray();
        for(char ch : chs){
            if(ch == '0') a++;
        }
        return a;
    }

    //盈利计划
    public int profitableSchemes(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int MOD = (int)Math.pow(10, 9) + 7;
        int[][][] dp = new int[len + 1][n + 1][minProfit + 1];
        for(int j = 0; j <= n; j++) dp[0][j][0] = 1;
        for(int i = 1; i <= len; i++){
            for(int j = 0; j <= n; j++){
                for(int k = 0; k <= minProfit; k++){
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(j >= group[i - 1]){
                        dp[i][j][k] += dp[i - 1][j - group[i - 1]][Math.max(0, k - profit[i - 1])];
                    }
                    dp[i][j][k] %= MOD;
                }
            }
        }
        return dp[len][n][minProfit];
    }

    //盈利计划(空间优化)
    public int profitableSchemes2(int n, int minProfit, int[] group, int[] profit) {
        int len = group.length;
        int MOD = (int)Math.pow(10, 9) + 7;
        int[][] dp = new int[n + 1][minProfit + 1];
        for(int j = 0; j <= n; j++) dp[j][0] = 1;

        for(int i = 1; i <= len; i++){
            for(int j = n; j >= 0; j--){
                for(int k = minProfit; k >= 0; k--){
                    if(j >= group[i - 1]){
                        dp[j][k] += dp[j - group[i - 1]][Math.max(0, k - profit[i - 1])];
                    }
                    dp[j][k] %= MOD;
                }
            }
        }
        return dp[n][minProfit];
    }

    //组合总数
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 1; i <= target; i++){
            for(int j = 0; j < n; j++){
                if(i - nums[j] >= 0) dp[i] += dp[i - nums[j]];
            }
        }
        return dp[target];
    }

    //不同的二叉搜索树
    public int numTrees(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 1;
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }
        return dp[n];
    }
}